// https://leetcode.cn/problems/ugly-number-ii/
// Created by ade on 2022/9/14.
// 给你一个整数 n ，请你找出并返回第 n 个 丑数 。 1 <= n <= 1690
// 输入：n = 10
// 输出：12
// 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
/*
 * 2 3 5
 * 4  6  10  *2
 * 6  9  15  *3
 * 10 15 25  *5
 * */

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    // 思路：丑数肯定都是2,3,5的倍数
    // 多路并归的解法
    // 三指针解法
    /*
     * 初始化 dp[1] = 1 因为刚开始3个指针都是从1倍开始算
     * 三指针的理解：每个丑数对应的指针落在地方
     * 定义三个指针初始值均为1，比如3,5,7 每次比较最小的丑数
     * 3对应的指针位置为1，且3 是最小的， 3入列， 并且对应3的指针位置后移一位
     * 5对应的指针位置为1，且5 是最小的， 5入列， 并且对应5的指针位置后移一位
     * 7对应的指针位置为1，且7 是最小的， 7入列， 并且对应7的指针位置后移一位
     * 因为指针对应在队列中都是丑数，所以乘积必然也是丑数
     * 对于重复的，需要进行判断，防止重复
     *
     * */
    int nthUglyNumber1(int n) {
        if (n <= 1) return 1;
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(min(2 * dp[p2], 3 * dp[p3]), 5 * dp[p5]);
            if (dp[i] == 2 * dp[p2]) {
                cout << "p2:";
                p2++;
            }
            if (dp[i] == 3 * dp[p3]) {
                p3++;
                cout << "p3:" << p3;
            }
            if (dp[i] == 5 * dp[p5]) {
                p5++;
                cout << "p5:" << p5;
            }
            cout << ",i:" << i << ",dp[i]:" << dp[i] << endl;
        }

        for (auto &i:dp) cout << i << ",";
        cout << endl;
        return dp[n];
    }

    //  优先队列 复杂度N*logN
    /*
     * 2,5,7
     * 1
     * 2
     *
     */
    int nthUglyNumber(int n) {
        if (n <= 1) return 1;
        vector<int> elems = {2, 3, 5};
        priority_queue<long, vector<long>, greater<long>> pq;
        pq.push(1);
        unordered_set<int> m = {};
        int top = 0;
        for (int i = 0; i < n; i++) {
            top = pq.top();
            while (m.count(top) > 0) {
                pq.pop();
                top = pq.top();
            }
            m.insert(top);
            pq.pop();
            for (int i = 0; i < elems.size(); i++) {
                pq.push((long) top * elems[i]);
            }
        }
        return top;
    }

};

int main() {
    Solution so;
    cout << so.nthUglyNumber(10);
    return 0;
}

